PROGRAMACIÓN
LÓGICA

Una programación declarativa

“La inferencia descendente [top-down] unifica la solución de problemas y la programación de ordenadores” (Robert Kowalski)


La Teoría de la Programación Lógica y el Lenguaje Prolog

La programación lógica

La idea principal de la programación lógica es la separación de la lógica y el mecanismo de ejecución (el control), informalmente expresado por Robert Kowalski [1979] mediante La lógica especifica el “qué”. El control especifica el “cómo”.

El objetivo que se pretende con esta separación es que el programador especifique lo que se conoce (las relaciones lógicas) y que sea el sistema el que responda automáticamente a las posibles consultas que se planteen a la Base de Conocimientos.

En los lenguajes imperativos tradicionales: En cambio, en los lenguajes orientados a la programación lógica, la situación es la contraria:
Lógica clausal

La programación lógica se basa en la lógica clausal, que es una restricción de la lógica de predicados de primer orden en la que las expresiones lógicas (claúsulas) son de tipo condicional y tienen la forma siguiente: el antecedente es de n términos conectados por el operador lógico “y” (and) y el consecuente consta de un sólo término. Son las llamadas “claúsulas de Horn” [1951], por Alfred Horn, que las estudió, y que tienen la forma La expresión h se denomina “cabecera” de la claúsula. El conjunto de expresiones ci se denomina “cuerpo” de la claúsula y son las condiciones necesarias para que se verifique el consecuente. Las comas entre las condiciones se interpretan como “y” lógico.

En las cláusulas de Horn no hay cuantificadores explícitos. Las variables libres se consideran que están cuantificadas universalmente.

Puede haber varias claúsulas de Horn con la misma cabecera. Esto quiere decir que la expresión h puede alcanzarse de formas alternativas, es decir, equivaldría al operador lógico clásico “o” (or).

Un hecho se puede considerar un caso particular de claúsula de Horn cuando el antecedente no existe (solo existe consecuente).

Puesto que en lógica clásica se define A→B = ¬A∨B, y puesto que se cumple la ley de De Morgan ¬(A∧B) = ¬A∨¬B, una cláusula de Horn es

c1, c2, …, cn → h = ¬ (c1 ∧ … ∧ cn) ∨ h = ¬c1 ∨ … ∨ ¬cn ∨ h

Una expresión lógica formada exclusivamente por disyunciones se denomina simplemente “cláusula”, donde un término y su contrario (o complemento) no pueden aparecer, porque si aparecieran, la cláusula sería una tautología.

Según la lógica clásica, toda fórmula lógica se puede expresar en forma normal disyuntiva (disyunción de conjunciones) o en forma normal conjuntiva (conjunción de disyunciones). Por lo tanto, una fórmula lógica se puede expresar como una conjunción de cláusulas.

Una cláusula en forma normal es una cláusula en forma normal de Skolem: los cuantificadores existenciales se han convertido en universales mediante ∃x P(x) = ¬∀x ¬P(x), donde todos los cuantificadores universales aparecen al comienzo de la expresión (forma prenexa), y donde se eliminan los cuantificadores universales al considerar que las variables están cuantificadas universalmente.

Los procesos de inferencia en programación lógica se basan en clásulas y en los principios de “unificación” y “resolución” de John Alan Robinson [1965].


Unificación

La unificación es un proceso de concordancia de patrones. La unificación trata de identificar expresiones sustituyendo variables (x, y, z) por constantes (a, b, c). El operador de unificación es el de sustitución (=). Dos expresiones (que contienen variables) se unifican si tienen una expresión común. Ejemplos: No es necesario calcular todos los unificadores posibles. Es suficiente considerar el unificador más general, es decir, un unificador tal que cualquier otro unificador se pueda obtener por instanciación de él. En el último ejemplo, el unificador más general es x = y = z = a.

La unificación descrita es de primer orden. La unificación de orden superior es cuando las variables representan funciones.

Robinson introdujo la unificación como una operación básica de su principio de resolución y desarrolló un algoritmo para calcular el unificador más general. El primer algoritmo de unificación de Robinson [1971] era poco eficiente. Posteriormente se han propuesto algoritmos más eficientes.


Resolución

La resolución es una regla de inferencia generalizada que infiere una nueva cláusula a partir de dos cláusulas que contienen términos complementarios (uno es la negación del otro). Formalmente: La nueva cláusula producida (de salida) se llama “resolvente” de las cláusulas de entrada, en la que desaparecen los términos complementarios.

La regla de resolución es una generalización del modus ponens: En efecto, como A→B se define como ¬A∨B, aplicando la regla de resolución: Ejemplos:
  1. De p∨q∨r y de ¬r se infiere p∨q.
  2. De p y de ¬p se infiere □ (la cáusula vacía), que indica contradicción.
En la lógica de predicados de primer orden, la regla de resolución es: En forma clausal, En la lógica de predicados de primer orden se realiza un proceso de unificación. En este caso, la unificación es x = a. Esta regla es la que rige en el silogismo.

SilogismoExpresión lógicaCláusula
Todo x que es P, es Q∀x P(x) → Q(x)¬P(x) ∨ Q(x)
a es PP(a)P(a)
a es QQ(a)Q(a)

La regla de resolución también adopta esta otra forma: En forma clausal, En este caso no hay unificación. Esta regla es la que rige en el silogismo.

SilogismoExpresión lógicaCláusula
Todo x que es P, es Q∀x P(x) → Q(x)¬P(x) ∨ Q(x)
Todo x que es P, es R∀x Q(x) → R(x)¬Q(x) ∨ R(x)
Todo x que es P, es R∀x P(x) → R(x)¬P(x) ∨ R(x)


Hiper-resolución

La hiper-resolución es una generalización de la resolución en la se combinan varios pasos de resolución en uno solo. La hiper-resolución básica consiste en dividir las clásulas en núcleos y electrones. Los núcleos tienen al menos un término negativo. Los electrones tienen todos términos positivos. La hiper-resolución se produce entre un núcleo y uno o más electrones. Hay un electrón por cada término negativo del núcleo. Un electrón puede ser utilizado en más de un paso intermedio. Ejemplo: La hiper-resolución generalizada consiste en considerar cláusulas que contengan pares de términos complementarios para eliminarlos a la vez. Por ejemplo:
Resolución por refutación

La regla de resolución se utiliza también para la demostración de teoremas por reducción al absurdo (resolución por refutación). Es un proceso de tipo ascendente (bottom-up): Por ejemplo, si tenemos la Base de Conocimientos Queremos demostrar S: Algún Perro ladra: ∃x Ladra(x)
  1. Convertimos la Base de Conocimientos y la sentencia ¬S en cláusulas:.


  2. Aplicando la resolución a los términos complementarios Ladra(x) y ¬Ladra(x), de las cláusulas primera y tercera, obtenemos como cláusula resolvente ¬Perro(x).

  3. Aplicando de nuevo la resolución a las cláusulas ¬Perro(x) y Perro(Pancho), obtenemos la cláusula vacía (□). Por lo tanto, la cláusula S es verdadera.
Otro ejemplo. Tenemos una Base de Conocimientos formada por las cláusulas Queremos demostrar r. Añadimos ¬r como nueva cláusula. Entonces tenemos: Por lo tanto, r es verdadero.


El lenguaje Prolog

El lenguaje de programación lógica más conocido es Prolog, que se basa en dos conceptos principales:
  1. La lógica clausal.
    Un programa Prolog se compone de una serie de claúsulas de Horn que establecen los hechos y las reglas de inferencia. Es la llamada “Base de Conocimientos”.

  2. Las inferencias automáticas.
    Es el control o proceso asociado a cómo el lenguaje obtiene la respuesta a una consulta relativa a una Base de Conocimientos. Las inferencias se basan en los principios de unificación y resolución.

    Las inferencias pueden ser de dos tipos: 1) con encadenamiento hacia adelante (deductivo, guiado por los datos); 2) con encadenamiento hacia atrás (inductivo, guiado por los objetivos). Estas inferencias también se denominan descendente (top-down) y ascendente (bottom-up), respectivamente.

    La inferencia hacia adelante es la más sencilla. La inferencia hacia atrás requiere un proceso más elaborado. Consiste en plantear un objetivo. Se acude a las cláusulas de Horn para buscar el objetivo como consecuente. Una vez localizado, se sustituye el objetivo por el cuerpo de la cláusula (el antecedente). Cada una de las condiciones del antecedente se convierten en subobjetivos, a los que se aplica el mismo mecanismo, y así sucesivamente hasta que se cumplan todas las condiciones. En el proceso hay que considerar todas las cláusulas de Horn en las que aparezcan el mismo consecuente (objetivo o subobjetivo). El resultado final es la composición de todas las sustituciones realizadas.
Las limitaciones de Prolog son:
La Programación Lógica con MENTAL

La notación de predicados

En lógica de predicados se suele utilizar la notación P(x1, … , xn), donde P es el predicado y x1, … , xn son los argumentos que intervienen en el predicado (n-ario). Cuando n es mayor que uno, esta notación no refleja claramente las relaciones semánticas de los argumentos con el predicado ni las relaciones de los argumentos entre sí.

Con un argumento, no hay problema: Hombre(Pepe) indica que Pepe es hombre. Con dos argumentos aparecen los problemas: en Padre(Pepe, David) se intuye que indica que Pepe es el padre de David, pero la expresión no lo refleja. Con tres argumentos, la situación se complica.

La notación más clara es la que hace uso de las primitivas de MENTAL. Ejemplos: Los hijos de Pepe podrían especificarse en una sola expresión: Pero la relación “Padre” es ascendente, lo que obliga a especificar en 4 expresiones los cuatro hijos de Pepe o utilizar el operador de distribución. Es más sencillo utilizar la notación descendente y especificar en una sola expresión los hijos de Pepe: Esta notación de tipo funcional tiene la ventaja de que permite también utilizar varios argumentos. Por ejemplo, Con Pepe/hombre y Pili/mujer.


Base de Conocimientos

Una Base de Conocimientos se compone de:
  1. Los conocimientos específicos. En la terminología clásica, una Base de Hechos. Se especifica mediante

    ( Hechos = ( h1…hn ) )

    Siendo los hi hechos concretos.

  2. Los conocimientos genéricos. En el enfoque clásico, se representan mediante una serie de reglas:

    ( Reglas = ( r1…rm ) )

    Siendo las ri reglas concretas.

    La expresión de una cláusula de Horn es en MENTAL especialmente homogénea:

    ⟨ (c1 → c2 → ... → cm) ⟩

    De forma compacta, se puede expresar así: ⟨ →⊣( c1…cm ) ⟩

    Especifica que si se cumplen las condiciones c1, … , c(m−1), entonces se cumple cm. Este último elemento podemos denominarlo ”elemento terminal” de una cláusula de Horn.

    Pero en MENTAL no se restringe a las clásulas de Horn ni solo a reglas. Las expresiones posibles solo están limitadas por las primitivas.

Ejemplo de Base de Conocimientos
  1. Conocimientos específicos (hechos).

    ( Hijos(Pepe Pili) = {JoséJuan Natalia Eva David} )

    ( Pepe/hombre Pili/mujer )

    ( JoséJuan/hombre Natalia/mujer Eva/mujer David/hombre )

    ( Hijos(Juanjo Natalia) = {Jorge Cristina} )

    ( Juanjo/hombre Jorge/hombre Cristina/mujer )

  2. Conocimientos genéricos (reglas):

    ⟨( (x ∈ Hijos(y z)) → ((Padre(x) = y) (Madre(x) = z))↓ )⟩

    ⟨( {x y}/Hermanos ← ((Padre(x) = Padre(y) ∧ (Madre(x) = Madre(y)) ∧ x≠y )⟩

    Dos personas son hermanos si tienen los mismos padres o porogenitores (Prog).

    ⟨( (Padre(x) = y) → (y/(Prog(x)) )⟩

    ⟨( (Madre(x) = y) → (y/(Prog(x)) )⟩

    Los consecuentes indican que y es un progenitor de x. Prog(x) es un calificador de y.

  3. Además podemos definir clases, que sirven para realizar consultas. Ejemplos:

    ⟨( (Hermanos(x) = Hijos(Padre(x) Madre(x)) ∪' {x} )⟩

    ⟨( (Prog(x) = {⟨( y ← y/(Prog(x)) )⟩} )⟩

    ⟨( (Ascendientes(x) = {⟨( (y z)↓ ← (x ∈ Hijos(y z)) )⟩} ∪ Ascendientes(y) ∪ Ascendientes(z) )⟩

    ⟨( (Descendientes(x) = {⟨( y ← ((y ∈ Hijos(x z) ∨ (y ∈ Hijos(z x)) )⟩} ∪ Descendientes(y) )⟩

El proceso automático de inferencia descendente

La ventaja de las expresiones genéricas es que, a partir de los datos iniciales (los hechos), se generan unos resultados, los cuales alimentan a las expresiones genéricas, que vuelven a producir nuevos resultados, y así sucesivamente hasta que los resultados se estabilicen. Todo este proceso tiene lugar de forma automática.
  1. Regla:
    ⟨( (x ∈ Hijos(y z)) → ((Padre(x) = y) (Madre(x) = z))↓ )⟩

    Resultados:

    Padre(JoséJuan) = Pepe) (Madre(JoséJuan) = Pili)
    Padre(Natalia) = Pepe) (Madre(Natalia) = Pili)
    Padre(Eva) = Pepe) (Madre(Eva) = Pili)
    Padre(David) = Pepe) (Madre(David) = Pili)
    Padre(Jorge) = Juanjo) (Madre(Cristina) = Natalia)

  2. Regla:
    ⟨( {x y}/Hermanos ← ((Padre(x) = Padre(y) ∧ (Madre(x) = Madre(y)) ∧ x≠y )⟩

    Resultados (combinaciones de los hermanos tomados de 2 en 2):

    {JoséJuan Natalia}/Hermanos
    {JoséJuan Eva}/Hermanos
    {JoséJuan David}/Hermanos
    {Natalia Eva}/Hermanos
    {Natalia David}/Hermanos
    {Eva David}/Hermanos
    {Jorge Cristina}/Hermanos

  3. Regla:
    ⟨( (Padre(x) = y) → (y/(Prog(x)) )⟩

    Resultados:

    Pepe/(Prog(JoséJuan))
    Pepe/(Prog(Natalia))
    Pepe/(Prog(Eva))
    Pepe/(Prog(David))
    Juanjo/(Prog(Jorge))
    Juanjo/(Prog(Cristina))

  4. Regla:
    ⟨( (Madre(x) = y) → (y/(Prog(x)) )⟩

    Resultados:

    Pili/(Prog(JoséJuan))
    Pili/(Prog(Natalia))
    Pili/(Prog(Eva))
    Pili/(Prog(David))
    Natalia/(Prog(Jorge))
    Natalia/(Prog(Cristina))

Consulta de la Base de Conocimientos

Una vez que se han generado los nuevos resultados a partir de los hechos y las reglas, se pueden realizar consultas. Las consultas pueden ser de tipo selección o tipo verificación.

Ejemplos de selección:
  1. ¿Quienes son los hijos de Pepe?
    Hijos(Pepe) // ev. {JoséJuan Natalia Eva David}

  2. ¿Quienes son los descendientes de Pepe?
    Descendientes(Pepe) // ev. {JoséJuan Natalia Eva David Jorge Cristina}

  3. ¿Quienes son los ascendientes de Jorge?
    Ascendientes(Jorge) // ev. {Pepe Pili Juanjo Natalia}

  4. ¿Quienes son los hermanos de David?
    Hermanos(David) // ev. {JoséJuan Natalia Eva}

  5. ¿Quienes son los progenitores de David?
    Prog(David) // ev. {Pepe Pili}

  6. ¿Cuáles son los padres con 2 o más hijos?
    {⟨( (x y)↓ ← (Hijos(x y))# ≥ 2 )⟩} // ev. {Pepe Pili Juanjo Natalia}
Ejemplos de verificación:
  1. ¿Pepe es hombre?
    (Pepe/Hombre)? // ev. α
    Pepe/Hombre está en la Base de Hechos.

  2. ¿Cuáles son los hijos de Pepe?
    Hijos(Pepe) // ev. {JoséJuan Natalia Eva David}
    Hijos(Pepe) está también en la Base de Hechos.

  3. ¿Pepe es el padre de David?
    (Padre(David) = Pepe)? // ev. α

  4. ¿David y Jorge son hermanos?
    ({David Jorge}/Hermanos)? // ev. θ
Si se desean obtener respuestas más claras, podemos hacer:

( (Verdadero =: α)(Falso =: θ) )
(Pepe/hombre)? // ev. Verdadero
(Pepe/mujer)? // ev. Falso


Otros atributos

Es posible asignar también otros atributos (por ejemplo, numéricos) y realizar consultas, como en las Bases de Datos. Por ejemplo, añadimos el atributo AñoNac (Año de Nacimiento) a los hijos de Pepe en la Base de Hechos: ¿Quienes son los hijos de Pepe nacidos en el año 1970 o posterior?
Regla de resolución

En MENTAL, la regla de resolución toma la forma siguiente: Es decir, dos expresiones disyuntivas del espacui abstracto que contengan dos términos opuestos, se sustituyen por una sola, en todo momento. Las dos expresiones que se fusionan no tienen relación entre sí. Solo comparten la propiedad de pertenecer al entorno.

Esta regla es general, válida para todo tipo de expresiones x, y, z, sean proposiciones o expresiones de la lógica de predicados de cualquier orden. Además es una regla de hiper-resolución generalizada para la lógica clausal proposicional. Por ejemplo, las cláusulas Se resuelven en dos pasos:
  1. ¬P∨¬Q∨R y Q∨C se transforman en ¬P∨R∨C.
  2. ¬P∨R∨C y P∨D se transforman en R∨C∨D.
Esta es otra demostración del poder de las expresiones genéricas.


Ventajas de MENTAL como lenguaje de programación lógica En conclusión, toda la complejidad de la programación lógica tradicional reside en:

Adenda

Sobre el principio de resolución de Robinson

El principio de resolución fue propuesto por Robinson en la publicación de 1965 “A Machine-Oriented Logic Based on the Resolution Principle” como fundamento para la demostración automática de teoremas. Desde entonces, este principio ha sido aplicado de forma general en IA (inteligencia artificial).

Su método de unificación y resolución eliminó en gran medida la explosión combinatoria que se produce en las demostraciones automáticas de teoremas, el excesivo número de cláusulas generadas, los llamados “universos Herbrand”. Realmente, el principio de resolución más que “inferir”, lo que hace es “fusionar” dos cláusulas en una, con el consiguiente ahorro de memoria y de tiempo de proceso.

Robinson preparó el terreno para la programación lógica en general y para el lenguaje Prolog en particular.

En los microprocesadores de Intel, AMD y otros, se utiliza un demostrador automático de teoremas (con la resolución de Robinson) para verificar que las operaciones matemáticas han sido dise⟩adas correctamente.


Más información sobre Prolog

El nombre de “Prolog” proviene de "Programación Lógica" y fue desarrollado en los 1970s por Alain Colmerauer y su equipo en la Universidad de Marsella, inspirado en gran parte por los trabajos sobre programación lógica de Robert Kowalski [1979], que a su vez se inspiró en los conceptos de unificación y resolución por refutación de Robinson.

El mecanismo de control utiliza un método de inferencia de encadenamiento hacia atrás (backwards chaining), pues para verificar una cierta expresión inicial (u objetivo), el sistema tiene que verificar si se cumplen todas las condiciones de las que depende (subobjetivos), que a su vez pueden depender o no de otras condiciones, etc. Lo que se tiene en definitiva es un árbol en el que se realiza una búsqueda en profundidad (depth-first). El lenguaje Prolog ha tenido una gran influencia en IA. Provocó una división entre los “Prologuistas” (los partidarios de Prolog) y los “Lispistas” (los partidarios de Lisp). Es el enfrentamiento entre dos paradigmas: el lógico (Prolog) y el funcional (Lisp). MENTAL es un lenguaje que contempla, de una manera simple, ambos paradigmas y muchos más. Es un paradigma universal que permite expresar paradigmas particulares. [ver Aplicaciones – Inteligencia Artificial – MENTAL, un Lenguaje de Inteligencia Artificial.]

Prolog se ha aplicado en numerosos campos: proceso de lenguaje natural, desarrollo de compiladores, sistemas expertos, búsqueda de patrones, razonamiento automático, demostración automática de teoremas, etc.

Existen numerosos dialectos de Prolog, algunos con mecanismos de control particulares. El llamado “Prolog de Edimburgo” es el dialecto normalizado “de facto”. También hay lenguajes “post-Prolog”, con conceptos más avanzados, como Prolog, que utiliza una extensión de la lógica clausal y una unificación de orden superior.

Prolog se convirtió en los años 1980s en el lenguaje oficial del proyecto japonés del ordenador de quinta generación, basado en IA, con hardware de proceso paralelo y Prolog como lenguaje lógico para razonamiento automático. El proyecto fue cancelado en 1993, tras 11 años de desarrollo.


Bibliografía